package now_coder.greedy.ncs;

import com.sun.org.apache.regexp.internal.RE;
import now_coder.dp.ncs.NC35;

import java.util.*;

public class NC37 {

    public static class Interval {
      int start;
      int end;
      Interval() { start = 0; end = 0; }
      Interval(int s, int e) { start = s; end = e; }

        @Override
        public String toString() {
            return "[" + start + ", " + end + ']';
        }
    }

    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if (intervals == null || intervals.size() == 0){
            return new ArrayList<>();
        }

        Comparator<Interval> comp = new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.start != o2.start)
                    return o1.start - o2.start;
                else
                    return o1.end - o2.end;
            }
        };

        intervals.sort(comp);
        ArrayList<Interval> ans = new ArrayList<>();
        int i = 0;

        while (i < intervals.size()){
            int left = intervals.get(i).start;
            int right = intervals.get(i).end;

            while (i < intervals.size() - 1 && intervals.get(i + 1).start <= right){
                right = Math.max(right, intervals.get(i + 1).end);
                i++;
            }

            ans.add(new Interval(left, right));
            i++;
        }

        return ans;
    }

    public static void main(String[] args) {
        ArrayList<Interval> intervals = new ArrayList<>();
        intervals.add(new Interval(10, 30));
        intervals.add(new Interval(10, 30));
        intervals.add(new Interval(50, 70));
        intervals.add(new Interval(50, 70));

        System.out.println(new NC37().merge(intervals));

        intervals.clear();
        intervals.add(new Interval(1, 4));
        intervals.add(new Interval(5, 9));
        intervals.add(new Interval(7, 10));

        System.out.println(new NC37().merge(intervals));
    }

}
